"""
题目：https://leetcode-cn.com/problems/validate-binary-search-tree/
    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    有效 二叉搜索树定义如下：
    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。   

    示例 1：
    输入：root = [2,1,3]
    输出：true
思路：递归方法——解决这道题时要考虑二叉搜索树的性质：左子树的所有值小于根节点的值，右子树的所有值大于根节点的值，因此我们可以采用递归的方法来做，
     判断根节点的左右子树是否分别是二叉搜索树。我们可以使用一个helper(node,lower,upper)函数，用来判断以node为根节点的子树是否是二叉搜索树，
     具体的说，就是这棵子树的所有值都在(l,r)的开区间内。因此如果node节点的值小于lower或者大于upper，那么该子树不是二叉搜索树，返回False。
     另外，当我们计算node的左子树的时候，由于左子树的所有值都小于根节点的值，因此此时的lower=lower,upper=node.val;
     同理，当我们计算node的右子树的时候，由于右子树的所有值都大于根节点的值，因此此时的lower=node.val,upper=upper。
     递归下去，即可验证该树是否是二叉搜索树。

时间复杂度：O(n)
空间复杂度：O(n)
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def helper(node,lower=float('-inf'),upper=float('inf')):
            if not node:
                return True
            val = node.val
            if val <= lower or val >= upper:
                return False
            if not helper(node.left,lower,val):
                return False
            if not helper(node.right,val,upper):
                return False
            return True
        return helper(root)